/*
现有一个不带头节点的单链表，该链表的头结点指针为pHead(每个结点两个分量：val值和next值)
编写一个函数完成以下任务：
1 编写一个函数getMinVal(ListNode * pHead, int &minx)，获得该链表当前最小值，放到minx中
2 编写一个链表排序函数sortLinkedList(ListNode * pHead)
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 为了使用INT_MIN宏

/* 定义链表节点结构体 */
typedef struct ListNode 
{
    int val;
    struct ListNode *next;
} ListNode;

/* 辅助函数：创建一个新节点 */ 
ListNode* createNode(int val) 
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) 
    {
        perror("Failed to allocate new node");
        exit(EXIT_FAILURE);
    }
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

/* 实现链表最小值的函数 */
int getMinVal(ListNode* pHead, int *minx) 
{
    if (pHead == NULL) 
        return 0; // 如果链表为空，则直接返回

    *minx = pHead->val; // 初始化最小值为头结点的值
    ListNode* current = pHead->next; // 从头结点的下一个节点开始遍历

    while (current != NULL) 
    {
        if (current->val < *minx) 
        {
            *minx = current->val; // 更新最小值
        }
        current = current->next; // 移动到下一个节点
    }
 
}


/* 实现链表排序函数（插入排序） */
ListNode* sortLinkedList(ListNode* pHead) 
{
    if (pHead == NULL || pHead->next == NULL) 
        return pHead; // 如果链表为空或只有一个节点，则不需要排序

    ListNode* dummy = createNode(INT_MIN); // 创建一个哑节点，方便处理头结点的插入
    dummy->next = pHead;
    ListNode *lastSorted = pHead, *curr = pHead->next; // lastSorted表示已排序部分的最后一个节点，curr表示当前待排序的节点

    while (curr != NULL) 
    {
        if (lastSorted->val <= curr->val) 
        {
            lastSorted = lastSorted->next; // 如果当前节点已经大于等于已排序部分的最后一个节点，直接移动lastSorted
        } 
        else 
        {
            ListNode* prev = dummy; // 从哑节点开始寻找插入位置
            while (prev->next->val <= curr->val) 
            {
                prev = prev->next; // 寻找插入位置
            }
            // 将curr插入到prev和prev->next之间
            lastSorted->next = curr->next;
            curr->next = prev->next;
            prev->next = curr;
        }
        curr = lastSorted->next; // 移动curr到下一个待排序节点
    }

    ListNode* sortedHead = dummy->next;
    free(dummy); // 释放哑节点
    return sortedHead;
}
